package com.zjj.algorithm.learning.atguigu.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 使用 Dijkstra（迪杰斯特拉） 求图中两个节点直接的最短路劲
 *
 * @author zjj_admin
 * @date 2023/1/3 20:27
 */
public class DijkstraAlgorithm {


    public static void main(String[] args) {
        char[] vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};

        int[][] weight = new int[][]{
                {-1, 9, -1, -1, -1, 5, 8},
                {9, -1, 6, -1, -1, 3, -1},
                {-1, 6, -1, 4, 2, 8, -1},
                {-1, -1, 4, -1, 12, -1, -1},
                {-1, -1, 2, 12, -1, 3, 12},
                {5, 3, -1, -1, 3, -1, 10},
                {8, -1, -1, -1, 12, 10, -1}
        };
        MinTree minTree = new MinTree();


        VisitedVertex res = minTree.dijkstra(vertex, weight, 'G');
        System.out.println("最短距离如下：");
        for (Map.Entry<Character, Integer> entry : res.dist.entrySet()) {
            System.out.println(entry);
        }
    }


}

/**
 * Dijkstra 算法辅助类，有关访问节点的信息
 */
class VisitedVertex {
    /**
     * 记录各个顶点是否被访问，0 表示没有被访问，1 表示已经被访问
     */
    Map<Character, Integer> alreadyVisited = new HashMap<>();

    /**
     * 每一个顶点的前一个顶点，会动态刷新
     */
    Map<Character, Character> preVisited = new HashMap<>();

    /**
     * 记录出发顶点到其他顶点的距离，也会动态更新
     */
    Map<Character, Integer> dist = new HashMap<>();

    /**
     * 每一个顶点在顶点数组中的 序号
     */
    Map<Character, Integer> pointIndex = new HashMap<>();

    /**
     * 构造器
     *
     * @param vertex     顶点信息
     * @param startPoint 起始顶点
     */
    public VisitedVertex(char[] vertex, char startPoint) {
        for (int i = 0; i < vertex.length; i++) {
            this.pointIndex.put(vertex[i], i);
            this.preVisited.put(vertex[i], null);
            if (vertex[i] == startPoint) {
                //设置出发顶点的访问距离为 0
                this.dist.put(vertex[i], 0);
                this.alreadyVisited.put(vertex[i], 1);
            } else {
                this.alreadyVisited.put(vertex[i], 0);
                this.dist.put(vertex[i], -1);
            }

        }
    }

    /**
     * point 顶点是否被访问过
     *
     * @param point
     * @return
     */
    public boolean isVisited(char point) {
        return this.alreadyVisited.get(point) == 1;
    }


    /**
     * 跟心从起点到 point 的距离
     *
     * @param point
     * @param len
     * @return
     */
    public void updateDist(char point, int len) {
        this.dist.put(point, len);
    }

    /**
     * 更新顶点 point 的前驱节点
     *
     * @param point
     * @param pre
     */
    public void updatePre(char point, char pre) {
        this.preVisited.put(point, pre);
    }

    /**
     * 获取出发顶点到 point 的距离
     *
     * @param point
     * @return
     */
    public int getDist(char point) {
        return this.dist.get(point);
    }

    /**
     * 获取 顶点 point 的索引
     *
     * @param point
     * @return
     */
    public int getIndex(char point) {
        return this.pointIndex.get(point);
    }

    /**
     * 根据索引获取顶点信息
     *
     * @param index
     * @return
     */
    public Character getPoint(int index) {
        for (Map.Entry<Character, Integer> entry : this.pointIndex.entrySet()) {
            if (entry.getValue() == index) {
                return entry.getKey();
            }
        }
        return null;
    }


    /**
     * 获取最新的起始顶点
     *
     * @return
     */
    public Character getNewStart() {
        int min = Integer.MAX_VALUE;
        char newStart = ' ';
        for (Map.Entry<Character, Integer> entry : this.alreadyVisited.entrySet()) {
            if (entry.getValue() == 0 && this.dist.get(entry.getKey()) != -1 && this.dist.get(entry.getKey()) < min) {
                min = this.dist.get(entry.getKey());
                newStart = entry.getKey();
            }
        }
        return newStart;
    }
}
